home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_src.lha / LEDA-3.1c-source / src / dict / _ch_hash1.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-17  |  5.0 KB  |  280 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _ch_hash1.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #include <LEDA/impl/ch_hash1.h>
  17.  
  18. //------------------------------------------------------------------------------
  19. //
  20. //  hashing with chaining and table doubling
  21. //
  22. //  S. Naeher (1994)
  23. //
  24. //------------------------------------------------------------------------------
  25.  
  26.  
  27. ch_hash1_elem ch_hash1::STOP;
  28.  
  29. #define NIL  GenPtr(this)
  30.  
  31. int ch_hash1::next_pow(int x) const
  32. { // return next power of 2
  33.   int result = 1;    
  34.   while ((x>>=1) > 0) result <<= 1;
  35.   return result;
  36.  }
  37.  
  38.  
  39. ch_hash1_item ch_hash1::lookup(GenPtr x) const
  40. { register ch_hash1_item q = table;
  41.  
  42.   STOP.k = x;
  43.  
  44.   if (int_type())
  45.   { q += (int(x) & table_size_1);  // table_size = power of 2
  46.     while (q->k != x) q = q->succ;
  47.    }
  48.   else
  49.   { q += (hash_fct(x) & table_size_1);
  50.     while (cmp(q->k,x)) q = q->succ;
  51.    }
  52.  
  53.   return (q == &STOP) ? 0 : q;
  54. }
  55.  
  56.  
  57. void ch_hash1::change_inf(ch_hash1_item p, GenPtr x)
  58. { clear_inf(p->i);
  59.   p->i = x;
  60.   copy_inf(p->i);
  61.  }
  62.  
  63. void ch_hash1::del(GenPtr x)
  64. { 
  65.   ch_hash1_item p = table + (int(x) & table_size_1);
  66.  
  67.   if (p->k == x)
  68.   { clear_key(p->k);
  69.     clear_inf(p->i);
  70.     p->k = NIL;
  71.     count--;
  72.     if (count == low_table) rehash(low_table);
  73.     return;
  74.   }
  75.  
  76.   STOP.k = x;
  77.  
  78.   if (int_type())
  79.      while (p->succ->k != x) p = p->succ;
  80.   else
  81.      while (cmp(p->succ->k,x)) p = p->succ;
  82.  
  83.   ch_hash1_item q = p->succ;
  84.  
  85.   if (q==&STOP) return;
  86.  
  87.   clear_key(q->k);
  88.   clear_inf(q->i);
  89.  
  90.   p->succ = q->succ;
  91.   delete q;
  92.   count--;
  93.   if (count == low_table) rehash(low_table);
  94.  }
  95.  
  96.  
  97. void ch_hash1::del_item(ch_hash1_item q)
  98. { register ch_hash1_item p = table + (hash_fct(q->k) & table_size_1);
  99.   clear_key(q->k);
  100.   clear_inf(q->i);
  101.   if (p==q) 
  102.      p->k = NIL;
  103.   else
  104.     { while(p->succ != q) p = p->succ;
  105.       p->succ = q->succ;
  106.       delete q;
  107.      }
  108.   count--;
  109.   if (count == low_table) rehash(low_table);
  110.  }
  111.   
  112.   
  113.   
  114.  
  115. ch_hash1_item ch_hash1::insert(GenPtr x, GenPtr y)
  116. { 
  117.   ch_hash1_item p = table + (int(x) & table_size_1);
  118.   ch_hash1_item q = p;
  119.  
  120.   STOP.k = x;
  121.  
  122.   if (int_type())
  123.      while (p->k != x) p = p->succ;
  124.   else
  125.      while (cmp(p->k,x)) p = p->succ;
  126.  
  127.   if (p != &STOP)
  128.   { clear_inf(p->i);
  129.     p->i = y;
  130.     copy_inf(p->i);
  131.     return p;
  132.    }
  133.  
  134.   count++;
  135.   copy_key(x);
  136.   copy_inf(y);
  137.  
  138.   if (q->k == NIL) 
  139.     { q->k = x;
  140.       q->i = y;
  141.      }
  142.   else
  143.     { q->succ = new ch_hash1_elem(x,y,q->succ);
  144.       q = q->succ;
  145.      }
  146.  
  147.   if (count == high_table) rehash(high_table);
  148.  
  149.   return q;
  150. }
  151.  
  152.  
  153.  
  154. void ch_hash1::destroy()
  155. { 
  156.   for(int i=0; i < table_size; i++) 
  157.   { ch_hash1_item p = table[i].succ;
  158.     ch_hash1_item q = p;
  159.     while (p != &STOP)
  160.     { clear_key(p->k);
  161.       clear_inf(p->i);
  162.       q = p;
  163.       p = p->succ;
  164.       delete q;
  165.     }
  166.    }
  167.   //delete[] table;
  168.   free(table);
  169. }
  170.  
  171.  
  172. void ch_hash1::init(int T)
  173. { 
  174.   register ch_hash1_item p;
  175.   register ch_hash1_item stop;
  176.  
  177.   table_size = T;
  178.   table_size_1 = T-1;
  179.  
  180.   low_table  = (T > 1024) ? T/2 : -1;
  181.   high_table = 2*T;
  182.  
  183.   //table = new ch_hash1_elem[table_size];
  184.   table = (ch_hash1_elem*)malloc(table_size*sizeof(ch_hash1_elem));
  185.  
  186.   stop = table + table_size;
  187.   for(p=table; p<stop; p++) 
  188.   { p->succ = &STOP;
  189.     p->k = NIL;
  190.   }
  191.  
  192.   count = 0;
  193. }
  194.  
  195.  
  196. void ch_hash1::rehash(int T)
  197. { 
  198.  
  199.   register ch_hash1_item p;
  200.   register ch_hash1_item q;
  201.   register ch_hash1_item r;
  202.   int i;
  203.  
  204.   ch_hash1_item old_table = table;
  205.   int old_table_size = table_size;
  206.   int old_count = count;
  207.  
  208.   init(T);
  209.  
  210.   if (int_type())
  211.      for (i=0; i<old_table_size; i++)
  212.      { p = old_table[i].succ;
  213.        while(p != &STOP)
  214.        { r = p->succ;
  215.          q = table + (int(p->k) & table_size_1);
  216.          p->succ = q->succ;
  217.          q->succ = p;
  218.          p = r;
  219.         }
  220.       }
  221.   else
  222.      for (i=0; i<old_table_size; i++)
  223.      { p = old_table[i].succ;
  224.        while(p != &STOP)
  225.        { r = p->succ;
  226.          q = table + (hash_fct(p->k) & table_size_1);
  227.          p->succ = q->succ;
  228.          q->succ = p;
  229.          p = r;
  230.         }
  231.       }
  232.  
  233.   ch_hash1_item stop = old_table+old_table_size;
  234.   for (p=old_table; p<stop; p++)
  235.     if (p->k != NIL) 
  236.     {  q = table + (int(p->k) & table_size_1);
  237.        if (q->k == NIL)
  238.         { q->k = p->k;
  239.           q->i = p->i;
  240.          }
  241.        else
  242.          q->succ = new ch_hash1_elem(p->k,p->i,q->succ);
  243.     }
  244.    
  245.   count = old_count;
  246.  
  247.   //delete[] old_table;
  248.   free(old_table);
  249. }
  250.  
  251.  
  252. ch_hash1::ch_hash1(const ch_hash1& D)
  253. { ch_hash1_item p;
  254.   init(D.table_size);
  255.   for (int i=0; i<table_size; i++)
  256.   { p = D.table[i].succ;
  257.     while(p != &(D.STOP))
  258.     { insert(p->k,p->i);
  259.       D.copy_key(p->k);
  260.       D.copy_inf(p->i);
  261.       p = p->succ;
  262.     }
  263.   }
  264. }
  265.  
  266.  
  267. ch_hash1& ch_hash1::operator=(const ch_hash1& D)
  268. { ch_hash1_item p;
  269.   clear();
  270.   for (int i=0; i<D.table_size; i++)
  271.   { p = D.table[i].succ;
  272.     while(p != &(D.STOP))
  273.     { insert(p->k,p->i);
  274.       p = p->succ;
  275.      }
  276.    }
  277.   return *this;
  278. }
  279.  
  280.